package com.xieyong.leetcode;

public class Leetcode3440 {

    public static void main(String[] args) {
        Leetcode3440 leetcode = new Leetcode3440();
        int eventTime = 21;
        int[] startTime = {7,10,16};
        int[] endTime = {10,14,18};
        int i = leetcode.maxFreeTime(eventTime, startTime, endTime);
        System.out.println(i);

    }
    public int maxFreeTime(int eventTime, int[] startTime, int[] endTime) {
        int n = startTime.length;
        boolean[] enableMove = new boolean[n];
        int maxFreeTimeLeft = 0, maxFreeTimeRight = 0;
        for (int i = 0; i < n; i++) {
            if (endTime[i] - startTime[i] <= maxFreeTimeLeft) {
                enableMove[i] = true;
            }
            maxFreeTimeLeft = Math.max(maxFreeTimeLeft, startTime[i] - (i == 0? 0 : endTime[i - 1]));
            if (endTime[n - i - 1] - startTime[n - i - 1] <= maxFreeTimeRight) {
                enableMove[n - i - 1] = true;
            }
            maxFreeTimeRight = Math.max(maxFreeTimeRight, (i == 0 ? eventTime : startTime[n - i]) - endTime[n - i - 1]);
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            int freeTime = endTime[i] - startTime[i];
            int left = i == 0 ? 0 : endTime[i - 1];
            int riget = i == n - 1 ? eventTime : startTime[i + 1];
            if (enableMove[i]) {
                res = Math.max(res, riget - left);
            } else {
                res = Math.max(res, riget - left - freeTime);
            }
        }
        return res;
    }


//    public int maxFreeTime(int eventTime, int[] startTime, int[] endTime) {
//        int res = 0;
//        int n = startTime.length;
//        int[] timelist = new int[n + 1];
//        timelist[0] = startTime[0];
//        int index = 1;
//        int maxFree = 0,maxFreeIndex = 0;
//        for (int i = 0,j = 0; i < n - 1 && j < n;) {
//            i++;
//            int freeTime = startTime[i] - endTime[j];
//            if (freeTime > maxFree) {
//                maxFree = freeTime;
//                maxFreeIndex = j;
//            }
//            timelist[index] = freeTime;
//            j++;
//            index++;
//        }
//        timelist[index] = eventTime - endTime[n - 1];
//        maxFree = Math.max(maxFree, eventTime - endTime[n - 1]);
//        for (int i = 0; i < n; i++) {
//            int itime = endTime[i] - startTime[i];
//            if (itime < maxFree) {
//                int freeTime = itime + timelist[i] + timelist[i + 1];
//                res = Math.max(res, freeTime);
//            }
//        }
//        return res;
//    }
}
